package org.thewares.collection.literature;

object Literature {

      // This is an implementation of Kaplan, Tarjan and Okasaki.
      // it is supposed to have O(1) concat, but this version doesn't seem to.
      // while asymtotically fast, it seem slow anyway: it does a lot of 
      // element reshuffling, so I haven't fixed it
      // It is possible that it would be fast if fixed, as concat is used in
      // the foopend methods... but I doubt it.
      abstract class CatDeque[+A] extends Deque[A] {
	    override def stringPrefix="CatDeque";


	    def apply(n: Int): A;
	    
	    def elements: Iterator[A];
	    def isEmpty: Boolean;
	    def length:Int;

	    def ::[B >: A](elem: B):CatDeque[B]={
		  this match{
			case d:FiveTuple[B] => {
			      val e=if (d.pr.length==6) {d.GP} else {d};
			      FiveTuple(elem :: e.pr, e.ld, e.md, e.rd, e.sf);
			}
			case Simple(b) => {
			      if (b.size <8){
				    Simple(elem :: b);
			      } else {
				    val (x,y,z)=b.splitEight;
				    FiveTuple(Buffer(elem,x),EmptyCat,Buffer(y),EmptyCat,Buffer(z));
			      }
			}
			case EmptyCat => {
			      Simple(Buffer.single(elem));
			}
		  }
	    }
	    

	    def +[B >: A](elem: B):CatDeque[B]={
 		  this match{
			case d:FiveTuple[A] => {
			      val e=if (d.sf.length==6) {d.GS} else {d};
			      FiveTuple(e.pr, e.ld, e.md, e.rd, e.sf + elem);
			}
			case Simple(b) => {
			      if (b.size <8){
				    Simple(b + elem);
			      } else {
				    val (x,y,z)=b.splitEight;
				    //println("split 8: "+b+" to "+b.splitEight);
				    FiveTuple(Buffer(x),EmptyCat,Buffer(y),EmptyCat,Buffer(z,elem));
			      }
			}
			case EmptyCat => {
			      Simple(Buffer.single(elem));
			}
		  }
	    }
	    

	    def peek:A;
	    def pop:CatDeque[A];
	    
	    def unshift[B >: A](elem: B):Deque[B] = elem :: this;
	    def head: A;
	    def tail: CatDeque[A];

	    override def equals(o: Any): Boolean={
		  o match {
			case d:CatDeque[_] => {
			      length==d.length && elements.zip(d.elements).forall{case (a,b) => a==b};
			}
			case _ => false;
		  }
	    }
	    override def hashCode(): Int={
		  (0 /: elements){case (i,a) => i ^ a.hashCode}
	    }

	    def dequeue: (A, CatDeque[A])=(head,tail);
	    def shift: CatDeque[A]=tail;    
	    def enqueue[B >: A](elem: B):CatDeque[B]= this+elem;
	    def peekPop: (A, CatDeque[A])=(peek,pop);

	    def push[B >:A](elem:B) = this + elem;

	    def naivePop:CatDeque[A]=pop;
	    def naiveTail:CatDeque[A]=tail;
	    
	    //fixme: should work, but not O(1).
	    def slowConcat[B >:A](other:Deque[B]) : CatDeque[B]= {
		  val me:CatDeque[B]= this;
		  (me /: other){(q,b) => b::q}
	    }

	    def :::[B >:A](other:Deque[B]) : CatDeque[B]= {
		  (other,this) match {
			case (FiveTuple(p1,l1,m1,r1,s1),FiveTuple(p2,l2,m2,r2,s2)) => {
			      val m=s1.peek :: p2.split(1)._1;
			      val s1rump=s1.pop; //size 2-5
			      val left= if (s1rump.length>3){
				    val (s11,s12)=s1rump.split(3);
				    l1+Triple(m1,r1,s11)+Triple(s12,EmptyCat,Buffer.empty);
			      } else {
				    l1+Triple(m1,r1,s1rump);
			      }
			      val p2rump=p2.tail;
			      val right=if (p2rump.length>3){
				    val (p11,p12)=p2rump.split(3);
				    Triple(p11,EmptyCat,Buffer.empty)::Triple(p12,l2,m2)::r2;
			      } else {
				    Triple(p2rump,l2,m2)::r2;
			      }
			      FiveTuple(p1,left,m,right,s2);
			} // FIVE FIVE
			case (that:CatDeque[B],_) => {
			      if (that.length>this.length){
				    (that /: this){(q,b) => q + b}
			      } else {
				    val me:CatDeque[B]=this;
				    (me /: that){(q,b) => b::q}
			      }
			}
			case _ =>  {
			      val me:CatDeque[B]=this;
			      (me /: other){(q,b) => b::q}
			}
		  }
	    }



	    def ++[B >: A](other:Seq[B])={
		  val me:CatDeque[B]= this;
		  (me /: other){(q,b) => q+b}
	    }

	    def reverseElements= {elements.toList.reverse.elements}; // SLOW
	    def reverseDeque=ReverseDeque(this);
	    def state={toString}
	    def depth= -1;
	    def nodes= -1;
      } // end CatDeque


      // sf is of size 1-8;
      case class Simple[+A](val sf:Buffer[A]) extends CatDeque[A]{
	    assert(!sf.isEmpty);

	    override def isEmpty=false;
	    def length=sf.length;
	    def elements=sf.elements;
	    def apply(i:Int)=sf.apply(i);

	    def peek:A= sf.peek;
	    def pop:CatDeque[A]= if (sf.size>1) Simple(sf.pop) else EmptyCat;
	    
	    def head: A = sf.head;
	    def tail: CatDeque[A] =if (sf.size>1) Simple(sf.tail) else EmptyCat;
	    
      }


      // pr,sf are of size 3-6, md is of size 2
      case class FiveTuple[+A] (val pr:Buffer[A], val ld:CatDeque[Triple[A]],val md:Buffer[A], val rd:CatDeque[Triple[A]],val sf:Buffer[A]) extends CatDeque[A]{
//	    println(state);
	    assert(pr.length >= 3 && pr.length <= 6)
	    assert(sf.length >= 3 && sf.length <= 6)
	    assert(md.length == 2)


	    override def state="FiveTuple("+pr+ld+md+rd+sf+")";

	    override def isEmpty=false;
	    // fixme borken speed.
	    def length=elements.collect.size;
	    def elements={
		  pr.elements++
		  ld.elements.flatMap(_.elements)++
		  md.elements ++
		  rd.elements.flatMap(_.elements)++
		  sf.elements;
	    }
	    // slow
	    def apply(n: Int): A= elements.drop(n).next();

	    /* green prefix version of this.  GP is ready for a tail or a :: operation 
	     * without cascade 
	     */
	    lazy val GP:FiveTuple[A]={
		  if (pr.length==6) { // overflow case: not ready for `::`
			val (x,y)=pr.split(4);
			FiveTuple(x,Triple(y,EmptyCat,Buffer.empty)::ld,md,rd,sf);
		  } else { // underflow case; not ready for tail
			// if pr>3 we wouldn't be here
			assert(pr.length==3);
			// one of ld,rd is nonempty, or we wouldn't be here
			assert(!(ld.isEmpty & rd.isEmpty));

			if (!ld.isEmpty){ //case 1
			      val t:Triple[A]=ld.head;
			      val el=if ((t.x.length==3) || !t.d.isEmpty){
				    ld.naiveTail
			      } else {
				    ld.tail
			      }
			      val (x,d1,y)=t.nonemptyFirst;
			      // "assume x is nonempty if t contains only one nonempty buffer", hmmm
			      if (x.length==3){ // case 1.1
				    val (x0,x1)=x.split(1);
				    FiveTuple(pr+x0(0), Triple(x1,d1,y) :: el, md, rd, sf);
			      } else { //case 1.2
				    if (x.length !=2){
					  println("popped triple is "+t.nonemptyFirst);
					  println("ld is "+ld);
				    }
				    assert(x.length==2); //failing
				    val p= pr + x(0)+ x(1);
				    if (y.isEmpty && d1.isEmpty){
					  FiveTuple(p,el,md,rd,sf);
				    } else {
					  val el1 = d1 ::: (Triple(y,EmptyCat,Buffer.empty) :: el)
					  FiveTuple(p,el1,md,rd,sf);
				    }
			      }
			} else { //case 2
			      // still on underflow: not ready for tail
			      // ld is empty, rd is not empty
			      assert(!rd.isEmpty);
			      
			      val t:Triple[A]=rd.head;
			      val (x,d,y)=t.nonemptyFirst;
			      val r=
				    if (x.size==3 || !d.isEmpty){
					  rd.naiveTail;
				    } else { // only 2 elements in t
					  rd.tail;
				    };
			      // assume x is nonempty if t consists of 1 nonempty buffer
			      if (x.length==3) { //case 2.1
				    val p= pr + md.head;
				    val m1= md.tail + x.head;
				    val x1=x.tail;
				    FiveTuple(p,EmptyCat,m1,Triple(x1,d,y) :: r,sf);
			      } else { // case 2.2 
				    assert(x.length==2);
				    val p=pr + md(0) + md(1);
				    val r1=
					  if (d.isEmpty & y.isEmpty){
						r;
					  } else {
						d ::: (Triple(y,EmptyCat,Buffer.empty) ::r);
					  }
				    FiveTuple(p,EmptyCat,x,r1,sf);
			      }
			}
		  }
	    } // end GP

	    lazy val GS:FiveTuple[A]={
		  if (sf.length==6) { // overflow case: not ready for `+`
			//val (x,y)=sf.split(4);
			//FiveTuple(x,Triple(y,EmptyCat,Buffer.empty)::ld,md,rd,sf);
			val (x,y)=sf.split(2);
			FiveTuple(pr,ld,md,rd +Triple(Buffer.empty,EmptyCat,x),y);
		  } else { // underflow case; not ready for pop
			// if sf>3 we wouldn't be here
			assert(sf.length==3);
			// one of ld,rd is nonempty, or we wouldn't be here
			assert(!(ld.isEmpty & rd.isEmpty));

			if (!rd.isEmpty){ //case 1
			      val t:Triple[A]=rd.peek;
			      val rightRump=if ((t.y.length==3) || !t.d.isEmpty){
				    rd.naivePop
			      } else {
				    rd.pop
			      }
			      val (x,d1,y)=t.nonemptyLast;
			      // "assume x is nonempty if t contains only one nonempty buffer", hmmm
			      if (y.length==3){ // case 1.1
				    val (y0,y1)=y.split(2);

				    FiveTuple(pr, ld, md, rightRump+Triple(x,d1,y0), y1(0)::sf);
			      } else { //case 1.2
				    assert(y.length==2);
				    val s= y(0) :: y(1) :: sf;
				    if (x.isEmpty && d1.isEmpty){
					  FiveTuple(pr,ld,md,rightRump,s);
				    } else {
					  val right = (rightRump + 
						       Triple(y,EmptyCat,Buffer.empty)) ::: d1;
					  FiveTuple(pr,ld,md,right,s);
				    }
			      }
			} else { //case 2
			      // still on underflow: not ready for pop
			      // rd is empty, ld is not empty
			      assert(!ld.isEmpty);
			      
			      val t:Triple[A]=ld.peek;
			      val (x,d,y)=t.nonemptyLast;
			      val leftRump=
				    if (y.size==3 || !d.isEmpty){
					  ld.naivePop;
				    } else { // only 2 elements in t
					  ld.pop;
				    };
			      // assume y is nonempty if t consists of 1 nonempty buffer
			      if (y.length==3) { //case 2.1
				    val s= md.peek :: sf;
				    val m1= y.peek :: md.pop ;
				    val y1=y.pop;
				    FiveTuple(pr,leftRump+Triple(x,d,y1),m1,EmptyCat,s);
			      } else { // case 2.2 
				    assert(y.length==2);
				    val s=md(0)::md(1) ::sf;
				    val left=
					  if (d.isEmpty & x.isEmpty){
						leftRump;
					  } else {
						(leftRump + Triple(x,EmptyCat,Buffer.empty)) :::d;
					  }
				    FiveTuple(pr,left,y,EmptyCat,s);
			      }
			}
		  }
	    }

	    def pop:CatDeque[A]=fancyPop;
	    def peek:A={ 
		  try {
			if (sf.isEmpty) {
			      assert(rd.isEmpty);
			      if (md.isEmpty) {
				    assert (ld.isEmpty);
				    pr.peek;
			      } else {
				    md.peek;
			      }
			} else {
			      sf.peek; //fixme?
			}
		  } catch {
			case e:Exception => {
			      println("fAILING TO PEEK");
			      println(this.state);
			      throw e;
			}
		  }
	    }


	    def fancyPop:CatDeque[A]={
		  if (sf.length >3){
			naivePop;
		  } else if ((sf.length == 3) && ld.isEmpty && rd.isEmpty){
			if (pr.length==3){
			      Simple(Buffer.fromThree(pr,md,sf.pop));
			} else {
			      FiveTuple(pr.pop, EmptyCat, pr.peek :: (md.pop), EmptyCat, md.peek :: (sf.pop))
			}
		  } else {
			GS.naivePop;
		  }
	    }

	    def head=pr.head;
	    def tail:CatDeque[A]=fancyTail;
	    def fancyTail:CatDeque[A]={
		  if (pr.length >3){
			naiveTail;
		  } else if ((pr.length == 3) && ld.isEmpty && rd.isEmpty){
			if (sf.length==3){
			      Simple(Buffer.fromThree(pr.tail,md,sf));
			} else {
			      FiveTuple(pr.tail + md.head , EmptyCat, md.tail + sf.head, EmptyCat, sf.tail)
			}
		  } else {
			GP.naiveTail;
		  }
	    }


	    override def naivePop:CatDeque[A]={
		  FiveTuple(pr, ld, md,rd,sf.pop);
	    }
	    override def naiveTail:CatDeque[A]={
		  FiveTuple(pr.tail, ld, md, rd, sf);
	    }

      } // end FiveTuple

      // the buffers are of size 0,2 or 3
      case class Triple[+A](val x:Buffer[A],val d:CatDeque[Triple[A]],val y:Buffer[A]) {
	    assert (!(x.isEmpty&d.isEmpty&y.isEmpty));
	    def elements:Iterator[A] ={
		  x.elements++
		  d.elements.flatMap(_.elements)++
		  y.elements
	    }
	    def nonemptyFirst=if (x.isEmpty & d.isEmpty) (y,d,x) else (x,d,y); 
	    def nonemptyLast=if(y.isEmpty & d.isEmpty) (y,d,x) else (x,d,y);
      }




      object Buffer {
	    def apply[A](a:RandomAccessSeq[A])={
		  new Buffer[A](a);
	    }
	    def apply[A,B >:A](x:B,a:RandomAccessSeq[A])={
		  val ret=new Array[B](a.length+1);
		  Array.copy(a,0,ret,1,a.length);
		  ret(0)=x;
		  new Buffer[B](ret);
	    }
	    def apply[A,B >: A](a:RandomAccessSeq[A],x:B)={
		  val ret=new Array[B](a.length+1);
		  try {
			Array.copy(a,0,ret,0,a.length);
		  } catch {
			case e:Exception =>{
			      println("L:"+a.getClass+" "+a.length+","+ ret.length);
			      println(a);
			      println(ret);
			      throw e;
			}
		  }
		  //println("ok:"+a.getClass+" "+a.length+","+ ret.length);
		  //println(a);
		  //println(ret);
		  ret(a.length)=x;
		  new Buffer[B](ret);
	    }
	    def fromThree[A](a:Buffer[A],b:Buffer[A],c:Buffer[A])={
		  val ret=new Array[A](a.length+b.length+c.length);
		  Array.copy(a.a,0,ret,0,a.length);
		  Array.copy(b.a,0,ret,a.length,b.length);
		  Array.copy(c.a,0,ret,a.length+b.length,c.length);
		  new Buffer[A](ret);
	    }
	    def single[A](x:A)={
		  val ret=new Array[A](1);
		  ret(0)=x;
		  new Buffer[A](ret);
	    }
	    val empty={
		  new Buffer[Nothing](new Array[Nothing](0));
	    }
      }


      final class Buffer[+A](val a :RandomAccessSeq[A]) {   
	    override def toString= a.toString;

	    //pre size 8
	    def splitEight={
		  (splice(a,0,3),splice(a,3,5),splice(a,5,8));
	    }

	    def apply(n:Int):A=a(n);
	    final def length=a.length;
	    final def size=a.length;
	    def elements=a.elements;
	    final def isEmpty= a.length == 0;
	    
	    def +[B >: A](elem: B):Buffer[B]= Buffer(a,elem);
	    def peek:A= a(length-1);

	    // pre: nonempty
	    def pop:Buffer[A]={ 
		  assert(!isEmpty);
		  val ret=new Array[A](length-1);
		  Array.copy(a,0,ret,0,length-1);
		  new Buffer[A](ret);
	    }

	    def ::[B >: A](elem: B):Buffer[B]=  Buffer(elem,a);

	    def head: A=a(0);
	    //pre: nonempy
	    def tail: Buffer[A]={
		  val ret=new Array[A](length-1);
		  Array.copy(a,1,ret,0,length-1);
		  new Buffer[A](ret);
	    }
	    def split(i:Int)=(Buffer(splice(a,0,i)),Buffer(splice(a,i)));
	    
      }

      /* fixme:  these are nonoptimal.  We say Buffer wants a RAS, but really, we 
          use Array.copy: so we more or less need an array.  (We couldn't 
          use a naked array, tho, because we are covarient.)
          RandomAccessSeq.slice returns a plain Seq... 
	  maybe need a class with a copy into array
	  */

      def splice[A](a:RandomAccessSeq[A], start:Int, end:Int):RandomAccessSeq[A]={
	a.slice(start,end).toArray;			  
      }
      
      def splice[A](a:RandomAccessSeq[A],start:Int):RandomAccessSeq[A]=
	    splice(a,start,a.length);


      case object EmptyCat extends CatDeque[Nothing] {
	    def apply(n:Int):Nothing=error("element "+n+" is not in EmptyCatDeque"); 
	    def elements=Iterator.empty;
	    override def isEmpty=true;
	    def length=0;
	    
	    // :: and + are inherited
	    
	    def peek:Nothing=error("EmptyCatDeque has no elements"); 
	    def pop:CatDeque[Nothing]=error("EmptyCatDeque has no elements"); 
	    
	    def head: Nothing=error("EmptyCatDeque has no elements"); 
	    def tail: CatDeque[Nothing]=error("EmptyCatDeque has no elements"); 

	    override val hashCode=0;
	    override def equals(other:Any)= other match{
		  case ed:CatDeque[_] => ed.length==0;
		  case _ => false;
	    }
      }

}
